\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

康托展开是一个比较常用的哈希技巧，可以将一个排列 \(a_1,a_2\cdots a_n\)
映射到一个整数 \(k\)，这个整数 \(k\) 就是这个排列在所有排列中的名次

由于它是双射的，所以也可以从一个整数还原这个整数所对应的全排列

\begin{itemize}
\item
  假定这个排列是由 \(n\) 个数组成的，那么有从一个整数 \(k\) 映射到第
  \(k\) 小的排列的方法：
\item
  将 \(k\) 写成 \(\sum^{n}_{i=1}rank_i(n-i)!\) 的形式，其中对于任意
  \(rank_i\)，有 \(0\leq rank_i\leq i\)
\item
  对于第 \(i\) 次操作，选择当前没有选过的第 \(rank_i\) 大的数加入排列
  (\textbf{权值线段树上二分})，所得的排列即为所求
\end{itemize}

\begin{itemize}
\item
  而根据 \(rank_i × (n-i)! <= k\) ，得 \(rank_i = k ÷ (n - i)!\)
\item
  有了 \(rank_i\) 后 ， \(k\) 也要相应减去 \(rank_i  × (n-i)!\) 以便求
  \(rank_{i-1}\)
\item
  即 \(k = k - rank_i × (n-i)!\) \(→\) \(k = k \% (n-i)\)
\end{itemize}

\end{document}
